package main.Q1001_1100;

import java.util.*;

public class Q1091_1100 {
    public static void main(String[] args) {
        System.out.println("Question1091：二进制矩阵中的最短路径");
        System.out.println("Question1092：");
        System.out.println("Question1093：");
        System.out.println("Question1094：拼车");
        System.out.println("Question1095：");
        System.out.println("Question1096：");
        System.out.println("Question1097：");
        System.out.println("Question1098：");
        System.out.println("Question1099：");
        System.out.println("Question1100：");
    }
}

class Question1091 {
    public boolean process(int[][] grid, Queue<int[]> queue, int r, int c) {
        int length = grid.length;
        if ((r + 1 == length - 1 && c + 1 == length - 1) || (r == length - 1 && c + 1 == length - 1) || (c == length - 1 && r + 1 == length - 1))
            return true;
        if (r - 1 >= 0 && c - 1 >= 0 && grid[r - 1][c - 1] == 0) queue.add(new int[]{r - 1, c - 1});//左上
        if (r - 1 >= 0 && grid[r - 1][c] == 0) queue.add(new int[]{r - 1, c});//正上
        if (r - 1 >= 0 && c + 1 < length && grid[r - 1][c + 1] == 0) queue.add(new int[]{r - 1, c + 1});//右上
        if (c - 1 >= 0 && grid[r][c - 1] == 0) queue.add(new int[]{r, c - 1});//左
        if (c + 1 < length && grid[r][c + 1] == 0) queue.add(new int[]{r, c + 1});//右
        if (r + 1 < length && c - 1 >= 0 && grid[r + 1][c - 1] == 0) queue.add(new int[]{r + 1, c - 1});//左下
        if (r + 1 < length && grid[r + 1][c] == 0) queue.add(new int[]{r + 1, c});//正下
        if (r + 1 < length && c + 1 < length && grid[r + 1][c + 1] == 0) queue.add(new int[]{r + 1, c + 1});//右下
        return false;
    }

    private int[] X = {0, 1, 1, 1, 0, -1, -1, -1};//方向数组
    private int[] Y = {1, 1, 0, -1, -1, -1, 0, 1};
    private int m, n;//方便记录长度而已，本题其实m和n是相等的。

    public int shortestPathBinaryMatrix(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        if (grid[0][0] == 1 || grid[m - 1][n - 1] == 1) return -1;//特殊情况特殊考虑，出口和入口被堵死
        if (m == 1 && grid[0][0] == 0) return 1;//只有一个0的情况
        int[][] v = new int[m][n];//识别数组
        Queue<int[]> a = new LinkedList();//队列，里面保存int数组为坐标
        a.add(new int[]{0, 0});//一开始将起点入队
        v[0][0] = 1;//起点标记为已经访问
        int step = 1;//理论上的初值
        while (!a.isEmpty()) {
            int s = a.size();//为step叠加用
            for (int i = 0; i < s; i++) {
                int[] temp = a.poll();//poll()方法会自动获取队首元素，且获取完自动出队
                int x = temp[0];
                int y = temp[1];
                for (int j = 0; j < 8; j++) {
                    int x1 = x + X[j];
                    int y1 = y + Y[j];
                    if (x1 >= 0 && x1 < m && y1 >= 0 && y1 < n && grid[x1][y1] == 0 && v[x1][y1] != 1) {//数组不越界，值为1，//没有被访问过才能入队
                        a.add(new int[]{x1, y1});//入队
                        v[x1][y1] = 1;//标记已访问！！！！！！！！！！！！不要忘记
                    }
                }
                if (x == m - 1 && y == n - 1) return step;//终止条件
            }
            step++;
        }
        return -1;//队列为空即为不能到达终点，返回-1
//        int length= grid.length;
//        if (grid[0][0]==1||grid[length-1][length-1]==1) return -1;//不能进入、不能出去
//        if (length==1) return 1;
//        int step=1;
//        Queue<int[]> queue=new LinkedList<>();
//        queue.add(new int[]{0,0});
//        while (!queue.isEmpty()){
//            int size=queue.size();//本层个数
//            for (int i=0;i<size;i++){//弹出本层，压入下一层
//                int[] cur=queue.poll();
//                grid[cur[0]][cur[1]]=1;//封路
//                if (process(grid,queue,cur[0],cur[1])){//若下一层到达出口
//                    return step+1;
//                }
//            }
//            step++;
//        }
//        return -1;
    }
}

class Question1094 {
    public boolean carPooling(int[][] trips, int capacity) {
        if (trips[0][0] > capacity) {
            return false;
        }
        Arrays.sort(trips, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] == o2[1]) {
                    return o1[2] - o2[2];
                }
                return o1[1] - o2[1];
            }
        });
        int n = trips.length;
        List<int[]> cur = new ArrayList<>();//当前车上的乘客组信息
        cur.add(trips[0]);
        int tempSum = trips[0][0];//车上总人数
        for (int i = 1; i < n; i++) {
            int[] station = trips[i];//车站等待上车的人信息
            if (station[0] > capacity) {
                return false;//等待人数超过车容量
            }
            for (int j = 0; j < cur.size(); j++) {//检查有无下车
                int[] a = cur.get(j);
                if (station[1] >= a[2]) {//车站是否是a组乘客的终点
                    tempSum -= a[0];//更新车上人数
                    a[0] = 0;//下车:模拟下车
                    a[1] = 1001;
                    a[2] = 1001;
                }
            }
            if (tempSum + station[0] > capacity) {//重新计算总人数，如果超过容量，则不行，否则更新车上人的信息
                return false;
            } else {//可以上车
                tempSum += station[0];
                cur.add(station);
            }
        }
        return true;
    }
}